home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / pcr / pcr4_4.lha / DIST / gc / GCmark.c < prev    next >
C/C++ Source or Header  |  1991-12-03  |  27KB  |  925 lines
  1. /* begincopyright
  2.   Copyright (c) 1988,1990 Xerox Corporation. All rights reserved.
  3.   Use and copying of this software and preparation of derivative works based
  4.   upon this software are permitted. Any distribution of this software or
  5.   derivative works must comply with all applicable United States export
  6.   control laws. This software is made available AS IS, and Xerox Corporation
  7.   makes no warranty about the software, its performance or its conformity to
  8.   any specification. Any person obtaining a copy of this software is requested
  9.   to send their name and post office or electronic mail address to:
  10.     PCR Coordinator
  11.     Xerox PARC
  12.     3333 Coyote Hill Rd.
  13.     Palo Alto, CA 94304
  14.     
  15.   Parts of this software were derived from code bearing the copyright notice:
  16.   
  17.   Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  18.   This material may be freely distributed, provided this notice is retained.
  19.   This material is provided as is, with no warranty expressed or implied.
  20.   Use at your own risk.
  21.   
  22.   endcopyright */
  23.   
  24. # include <signal.h>
  25. # include <sys/types.h>
  26. # include <sys/times.h>
  27. # include <sys/time.h>
  28. # include <sys/resource.h>
  29. # include <sys/timeb.h>
  30.  
  31. # include "xr/GCPrivate.h"
  32. # include "xr/Threads.h"
  33.  
  34. #define I_HOLD_ML(ml) (((XR_ML)(ml))->ml_holder == XR_currThread)
  35.  
  36. # define COUNT_CACHE_HITS
  37. # undef COUNT_CACHE_HITS
  38.  
  39. /*
  40.  * Derived from the Boehm-Demers collector, with some of C. Hauser's code,
  41.  * and probably some of Mark Weiser's code.
  42.  * Boehm, April 17, 1990 5:34:55 pm PDT
  43.  */
  44.  
  45. /*
  46.  * This file contains the functions:
  47.  *      GC_mark(alignment)
  48.  *      GC_mark_all(b,t,alignment,mark_clean)
  49.  *      GC_get_current_sp()
  50.  */
  51.  
  52. /* Leaving these defined enables output to stderr.  In order of */
  53. /* increasing verbosity:                                        */
  54. #define DEBUG            /* Verbose debugging output */
  55. #undef DEBUG
  56. #define DEBUG2           /* EXTREMELY verbose debugging output */
  57. #undef DEBUG2
  58.  
  59.  
  60. /* Return a rough approximation to the stack pointer.  A hack,  */
  61. /* but it's semi-portable.                                      */
  62. word * GC_get_current_sp()
  63. {
  64.     word x;
  65.     return(&x);
  66. }
  67.  
  68. /*
  69.  *  Proc to see how much page swapping is going on ... returns the 
  70.  *  number of page faults being serviced
  71.  */
  72. unsigned long GC_check_faults()
  73. {
  74.     struct rusage usage;
  75.     
  76.     getrusage(RUSAGE_SELF, &usage);    /* NOT XR_GetRUsage(...)! */
  77.     return(usage.ru_majflt);
  78. }
  79.  
  80.  
  81. /*
  82.  *  Convert the mark stack to bucket form.
  83.  */
  84.  
  85. /*
  86.  * the performance is insensitive to the SEGSIZE and WINDOW
  87.  * for experiments tried this far.
  88.  */ 
  89. #define SEGSIZE 0x100000
  90.    /* size of the segment recorded in each hash bucket */
  91.    
  92. static unsigned long WINDOW = 4;
  93.    /* number of segments inspected together during marking */
  94.    /* not #define'd for ease of experimentation */
  95.    
  96. #define BOUNDARY 0xffffffff 
  97.    /* non-pointer value marking edges of buckets */
  98.    
  99. static unsigned long **alloc;
  100.    /* 
  101.     * all allocation in this file is done below GC_mark_stack_top,
  102.     * by moving alloc to lower addresses.
  103.     */
  104.     
  105. static unsigned long **buckets;
  106.    /*
  107.     * buckets is the address of an array of pointers to hashbuckets.
  108.     * each bucket contains possible pointers into a single SEGSIZE segment
  109.     * of the heap.
  110.     */
  111.     
  112. static int removals;
  113. static int insertions;
  114.    /*
  115.     * insertions-removals is number of candidates remaining to be
  116.     * processed.  Kept separately for statistics gathering.
  117.     */ 
  118.     
  119. static char * GC_my_heaplim;
  120.    /*
  121.     * GC_heaplim when marking started.  Pointers beyond this can safely
  122.     * be ignored, since they must have been created later.  Thus the page
  123.     * in which they were stored will have been dirtied.
  124.     */
  125.     
  126. #ifdef PRINTSTATS
  127.    static unsigned bucketsallocated;
  128. #endif
  129.  
  130.  
  131.     
  132. #define PTRSPERBUCKET 252
  133.    /*
  134.     * no experimentation has been done on the sensitivity of performance to 
  135.     * this value.
  136.     */
  137.     
  138. typedef struct {
  139.   unsigned long *prev;
  140.       /* Points to last pointer slot in prev bucket */
  141.   unsigned long topmark;
  142.   unsigned long *ptrs[PTRSPERBUCKET];
  143.   unsigned long bottommark;
  144.   unsigned long *next;
  145.       /* If in use, points to topmark of next bucket.        */
  146.     /* If free, points to beginning of next free bucket     */
  147. } hashbucket;
  148.   
  149. static hashbucket * bucket_free_list = NIL;
  150.  
  151. hashbucket * allocbucket()
  152. {
  153.     hashbucket * new;
  154.     
  155.     if (bucket_free_list != NIL) {
  156.       new = bucket_free_list;
  157.       bucket_free_list = (hashbucket *) (bucket_free_list -> next);
  158.     } else {
  159.       /* claim space for a bucket from the allocation stack */
  160.         alloc -= (sizeof(hashbucket)/sizeof(unsigned long *));
  161.         new = (hashbucket *)alloc;
  162.     }
  163.  
  164. if((unsigned long) new < 0x10000000) GC_abort("allocbucket");
  165.     return(new);
  166. }
  167.  
  168. void freebucket(b)
  169.     hashbucket *b;
  170. {
  171.     b -> next = (unsigned long *) bucket_free_list;
  172.     bucket_free_list = b;
  173. }
  174.   
  175.  
  176. static unsigned long *newbucket(prevbucket)
  177.    unsigned long *prevbucket;
  178.    /*
  179.     * returns an empty hash bucket pointing back at prevbucket
  180.     */ 
  181. {
  182.    hashbucket *new;
  183.    int i;
  184.    
  185.       new = allocbucket();
  186.      
  187.    /* chain buckets hashing to the same position */ 
  188.       new->prev = prevbucket;
  189.       new->next = NIL;
  190.       
  191.    /* insert boundary marks and initialize contents to empty */
  192.       new->topmark = (new->bottommark = BOUNDARY);
  193.       for (i=0; i < PTRSPERBUCKET; i++) new->ptrs[i] = NIL;
  194.       
  195. #ifdef PRINTSTATS
  196.       ++bucketsallocated;
  197. #endif
  198.    
  199.    /* return a pointer to the topmark slot (making this bucket empty) */
  200.       return (&(new->topmark));
  201. }
  202.   
  203.  
  204. static void insert(p) 
  205.    unsigned long p;
  206.    /*
  207.     * inserts candidate pointer p in the bucket structure
  208.     */
  209. {
  210.    unsigned long **b;
  211.    unsigned long *slotptr;
  212.    struct hblk * h = HBLKPTR(p);
  213.    unsigned long heapoffset = p - (unsigned) GC_heapstart;
  214.    
  215.    if (p >= (unsigned long)GC_my_heaplim) return;
  216.    
  217.    /* Note that the bucket we use corresponds to the actual pointer */
  218.    /* we found, and not necessarily the start address of the heap   */
  219.    /* block.  This may cause the marking process to exhibit         */
  220.    /* slightly less locality.  But it saves some moderately         */
  221.    /* expensive calculation here.                       */
  222.  
  223.    b = buckets+heapoffset/SEGSIZE;
  224.       /* candidate bucket */
  225.      
  226.    slotptr = ++(*b);
  227.       /* candidate position in the hashbucket to record p */
  228.       
  229.    if (*slotptr == BOUNDARY) { /* full: slotptr is pointing
  230.                                   at the bottom mark  */
  231.       slotptr++;
  232.          /* move along to the next field */
  233.       if (*slotptr == (unsigned) NIL) { /* no next bucket yet */
  234.          *slotptr = (unsigned) newbucket(slotptr-2);
  235.             /* create one and chain together */
  236.          };
  237.       
  238.       /* assert: *slotptr == BOUNDARY; (the topmark) */
  239.       slotptr = ((unsigned long *) (*slotptr))+1;
  240.          /* move to the first real slot */ 
  241.       *b = slotptr;
  242.          /* link into hash table */
  243.       };
  244.       
  245.    *slotptr = p;
  246.       /* what we really wanted to do from the start */ 
  247.    insertions++;
  248. }
  249.     
  250.     
  251. static unsigned long remove(b)
  252.    unsigned long **b;
  253.    /*
  254.     * return a candidate pointer from bucket *b points inside, NIL if none
  255.     */
  256. {
  257.    unsigned long *slotptr;
  258.    slotptr = *b;
  259.    if (slotptr == NIL) return (unsigned long)NIL;
  260.                          /* no heap blocks in this bucket */
  261.    if (*slotptr == BOUNDARY) { /* at the topmark */
  262.       if (*(slotptr-1) == (unsigned long)NIL) {
  263.         return (unsigned long)NIL; /* no previous bucket */
  264.       } else {
  265.         hashbucket * ob = (hashbucket *)(slotptr - 1);
  266.         
  267.         slotptr = (unsigned long *) *(slotptr-1); /* move to previous bucket */
  268.         if ((ob -> next) != NIL) {
  269.           /* We leave ob around to avoid lots of allocation around boundary */
  270.           /* We deallocate next bucket, to avoid wasting stack space.        */
  271.             freebucket(ob -> next - 1);
  272.             ob -> next = NIL;
  273.          }
  274.  
  275.       }
  276.    };
  277.    *b = slotptr-1; /* remove an item from the bucket */ 
  278.    removals++;
  279.    return *slotptr; /* return the item */
  280. } 
  281.   
  282.  
  283. static void docandidate();
  284.  
  285. # ifdef USE_HEAP
  286.    --> The careful marking stuff currently assumes that we use the process
  287.        stack for marking
  288. # endif       
  289.  
  290. static void carefulmark(alignment)
  291. int alignment;
  292.    /*
  293.     * for marking when page faults are occurring; 
  294.     */
  295. {
  296.    unsigned nbuckets;
  297.    unsigned long **bucketlim;
  298.  
  299.    register struct obj *p; /* pointer to current object to be marked */
  300.    long heapsize; /* Unlike the global, this includes blocks not administered */
  301.              /* by us.                              */
  302.    unsigned passcount = 0;
  303.   
  304.    struct hblk **blocklim; 
  305.    unsigned blockcount = 0; /* number of heap blocks */
  306.    unsigned startfaults = GC_check_faults();
  307.    unsigned markfaults;
  308.   
  309.    if (GC_mark_stack_top == GC_mark_stack_bottom) return;
  310.    insertions = removals = 0;
  311.    bucketsallocated = 0;
  312.    GC_my_heaplim = GC_heaplim;
  313.    heapsize = GC_my_heaplim - GC_heapstart;
  314.    alloc = (unsigned long **) GC_mark_stack_top;
  315.    bucket_free_list = NIL;
  316.   
  317.  
  318.   {  
  319.     /* construct the empty hash table for candidate pointers */
  320.      unsigned long **b;
  321.      
  322.      nbuckets = (heapsize + SEGSIZE-1) / SEGSIZE;
  323.      bucketlim = alloc;
  324.      buckets = (alloc = alloc-nbuckets); /* claim space for nbuckets */
  325.      for (b = buckets; b < bucketlim; b++) {
  326.         *b = newbucket(NIL);
  327.      };
  328.    }
  329.     
  330.   { /* insert all the initial candidates */
  331.      register word * lim;
  332.      register word * p;
  333.      
  334.      if (sizeof(hashbucket) % sizeof(word) != 0) GC_abort("carefulmark 0");
  335.      while (GC_mark_stack_top < GC_mark_stack_bottom) {
  336.         lim = (word *)(((char *)GC_mark_stack_top) + sizeof (hashbucket));
  337.         p = GC_mark_stack_top;
  338.         if (lim > GC_mark_stack_bottom) {
  339.             while (p < GC_mark_stack_bottom) insert (*p++);
  340.         } else {
  341.             while (p < lim) insert (*p++);
  342.             /* Recycle this section of the mark stack for hash buckets */
  343.               freebucket((hashbucket *)GC_mark_stack_top);
  344.         }
  345.         GC_mark_stack_top = p;
  346.      };
  347.   };
  348.     
  349.   {
  350.      /*
  351.       * Now all the items from the initial stack have been put in buckets;
  352.       * Start processing them;
  353.       */
  354.      
  355.      
  356.      while (insertions != removals) {
  357.         unsigned long **lowlim, **highlim;
  358.                 /* limits of current confined analysis */
  359.         unsigned long **b; /* current hash slot to inspect */
  360.         
  361. #       ifdef PRINTSTATS
  362.           ++passcount;
  363. #       endif
  364.         highlim = buckets+WINDOW;
  365.         if (highlim >= bucketlim) highlim = buckets;
  366.         lowlim = b = buckets;
  367.     
  368.         while (lowlim < bucketlim) {
  369.            p = (struct obj *) remove(b);
  370.            if (p == (struct obj *)NIL) {
  371.                b++;
  372.                if (b == bucketlim) b = buckets;
  373.                if (b == highlim) {
  374.                    while (lowlim < bucketlim && 
  375.                           (*lowlim == NIL
  376.                            || (unsigned) (**lowlim) == BOUNDARY)) {
  377.                        highlim++;
  378.                        if (highlim==bucketlim) highlim=buckets;
  379.                        lowlim++;
  380.                    }; /* while ((lowlim<bucketlim) . . . */
  381.                    b = lowlim;
  382.                 }; /* if (b==highlim) */
  383.            } else /* p != NIL */ { 
  384.               docandidate(p, alignment);
  385.            };
  386.         }; /* while (lowlim < bucketlim) */
  387.      }; /* while (insertions != removals) */
  388. #    ifdef PRINTSTATS
  389.      { 
  390.         markfaults = GC_check_faults() - startfaults;
  391.         GC_markfaults += markfaults;
  392.         GC_printf("Ending mark phase.  Faults: %d, Insertions: %d\n",
  393.                   markfaults, insertions);
  394.         GC_printf("Buckets: %d, Passes: %d\n",bucketsallocated, passcount);
  395.      };
  396. #    endif
  397.   };
  398. } /* carefulmark */
  399.   
  400. static void docandidate(p, alignment)
  401. struct obj *p;
  402. int alignment;
  403. {
  404.    
  405.    long sz;
  406.    long word_no;
  407.    struct hblk * h;
  408.    bool is_atomic;
  409. #  ifdef SEPARATE_HEADERS
  410.      register struct hblkhdr * hhdr;
  411. #  endif
  412. #  ifdef COUNT_CACHE_HITS
  413.      /* Hard to print here, put must be defined for GCcheck_ptr.c */
  414.      long map_cache_hits = 0;
  415.      long map_cache_misses = 0;
  416. #  endif
  417.  
  418.    
  419.     /* Check whether p points to a valid unmarked object.  Continue to the   */
  420.     /* next iteration if not.  Set h to point to the beginning of the block  */
  421.     /* containing p.  Set word_no to the offset of the beginning of the      */
  422.     /* object.  Set sz to the size of the object in words.             */
  423.     /* Set is_atomic and hhdr.                             */
  424. #     define CONTINUE_M return
  425. #     ifdef BLACK_LIST
  426. #     define CONTINUE goto register_bad_c
  427. #     else
  428. #       define CONTINUE return
  429. #     endif
  430. #     include "GCcheck_ptr.c"
  431. #     undef CONTINUE
  432. #     undef CONTINUE_M
  433.    
  434. #  ifdef GATHERSTATS
  435.      GC_my_objects_in_use++;
  436. #  endif
  437.    set_mark_bit(h, word_no);
  438.    if (is_atomic) {
  439.       /* Atomic object */
  440. #     ifdef GATHERSTATS    
  441.       GC_my_atomic_in_use += sz;
  442. #     endif      
  443.       return;
  444.    };
  445.    GC_my_composite_in_use += sz;
  446.    {  
  447.       /* Mark from fields inside the object */
  448.     register struct obj ** q;
  449.     register struct obj * r;
  450.     register long lim;   /* Should be struct obj **, but we're out of */
  451.                  /* A registers on a 68000.                   */
  452.  
  453. #       ifdef INTERIOR_POINTERS
  454.       /* Adjust p, so that it's properly aligned */
  455.         p = ((struct obj *)(((word *)h) + word_no));
  456. #       endif
  457. #       ifdef UNALIGNED
  458.       lim = ((long)(&(p -> obj_component[sz]))) - 3;
  459. #       else
  460.       lim = (long)(&(p -> obj_component[sz]));
  461. #       endif
  462.     for (q = (struct obj **)(&(p -> obj_component[0]));
  463.                     q < (struct obj **)lim;) {
  464.         r = *q;
  465.         if (quicktest(r)) {
  466. #               ifdef DEBUG2
  467.             GC_vprintf("Found plausible nested pointer");
  468.             GC_vprintf(": 0x%X inside 0x%X at 0x%X\n", r, p, q);
  469. #               endif
  470.         insert(r);
  471.         }
  472. #           ifdef UNALIGNED
  473.         q = ((struct obj **)(((long)q)+alignment));
  474. #           else
  475.         q++;
  476. #           endif 
  477.     }
  478.    }; /* mark from fields inside object */
  479. # ifdef BLACK_LIST
  480.     return;
  481.     register_bad_c:
  482.         /* p looks like a pointer, but doesn't point to an    */
  483.         /* objects.                        */
  484.         if ((unsigned long)p
  485.             >= (unsigned long) ((struct hblk *) GC_heapstart + MAP_SIZE)) {
  486.             return;
  487.         }
  488.         GC_add_to_black_list(p);
  489. # endif
  490. } /* docandidate */ 
  491.   
  492.  
  493. static unsigned toomanyfaults = 1000;
  494.  
  495.  
  496. /*
  497.  * Clear mark bits in all allocated heap blocks.
  498.  * Assumes I do not hold GC_allocate_ml, but all reclaim lists are
  499.  * empty.  Thus nobody will look at mark bits while we're
  500.  * running, and hb_busy will not get set.  It may be
  501.  * set when we start, but then we simply wait.
  502.  */
  503. void GC_clear_marks()
  504. {
  505.     register int j;
  506.     register struct hblk **p;
  507.     register struct hblk *q;
  508.  
  509.     if (I_HOLD_ML(&GC_allocate_ml)) {
  510.         XR_Panic("GC_clear_marks 0");
  511.     }
  512.  
  513.     XR_MonitorEntry(&GC_allocate_ml);
  514.     for (q = (struct hblk *) GC_heapstart; ((char*)q) < GC_heaplim; q++)
  515.       if (is_hblk(q)) {
  516.         while (hb_busy(q)) {
  517.             /* There are better ways to synchronize.  But empirically         */
  518.             /* this happens about .2 times during the life of a Cedar world. */
  519.         XR_MonitorExit(&GC_allocate_ml);
  520.             GC_printf("GC_clear_marks waiting for reclaim\n");
  521.             XR_PauseAbortable(1);
  522.         XR_MonitorEntry(&GC_allocate_ml);
  523.         }
  524.  
  525. #       ifdef VISUALIZE
  526.         /* redisplay all marked objects as allocated */
  527.         undisplay_marks(q);
  528. #       endif
  529.         for (j = 0; j < MARK_BITS_SZ; j++) {
  530.         hb_marks(q)[j] = 0;
  531.         }
  532.     }
  533.     XR_MonitorExit(&GC_allocate_ml);
  534.  
  535.     /* In use counts track number of marked words.  Reset private counters. */
  536.     GC_my_atomic_in_use = GC_my_composite_in_use = 0;
  537.     GC_my_objects_in_use = 0;
  538. }
  539.  
  540.  
  541. /* Mark all objects corresponding to pointers between GC_mark_stack_bottom */
  542. /* and GC_mark_stack_top.  Assume that nested pointers are aligned      */
  543. /* on alignment-byte boundaries.                                           */
  544. /* The mark stack is empty when mark returns.                              */
  545. void GC_mark(alignment)
  546. int alignment;
  547. {
  548.   register long sz;
  549.   extern char end, etext;
  550.   register struct obj *p; /* pointer to current object to be marked */
  551.   unsigned startfaults;
  552.   unsigned markfaults;
  553. # ifdef COUNT_CACHE_HITS
  554.       long map_cache_hits = 0;
  555.       long map_cache_misses = 0;
  556. # endif
  557. # ifdef SEPARATE_HEADERS
  558.       register struct hblkhdr * hhdr;
  559. # endif
  560.  
  561.   bool is_atomic;
  562.   /* Register copies of frequently referenced globals */
  563.   /* Referenced primarily from inside macros.         */
  564.     register char * GC_heapstart_reg;
  565.     register word * GC_mark_stack_top_reg;
  566. #   ifdef GATHERSTATS
  567.       register long GC_my_objects_in_use_reg;
  568. #   endif
  569.     
  570.  
  571. # ifdef VISUALIZE
  572.     window_update();
  573. # endif
  574.   
  575.   if ( GC_markCarefully ) {
  576.       carefulmark(alignment);
  577.       return;
  578.   }
  579.   startfaults = GC_check_faults();
  580.   
  581.   /* Set up "global" registers */
  582.     GC_heapstart_reg = GC_heapstart;
  583.     GC_mark_stack_top_reg = GC_mark_stack_top;
  584. #   define GC_mark_stack_top GC_mark_stack_top_reg
  585. #   define GC_heapstart GC_heapstart_reg
  586. #   ifdef GATHERSTATS
  587.       GC_my_objects_in_use_reg = GC_my_objects_in_use;
  588. #   endif
  589.   
  590.   while (GC_mark_stack_top != GC_mark_stack_bottom) {
  591.      register long word_no;
  592.      register struct hblk * h;
  593.  
  594. #    ifdef USE_STACK
  595.     p = (struct obj *)(*GC_mark_stack_top++);
  596. #    else
  597. #     ifdef USE_HEAP
  598.     p = (struct obj *)(*GC_mark_stack_top--);
  599. #     else
  600.     --> fixit <--
  601. #     endif
  602. #    endif
  603.     /* Check whether p points to a valid unmarked object.  Continue to the   */
  604.     /* next iteration if not.  Set h to point to the beginning of the block  */
  605.     /* containing p.  Set word_no to the offset of the beginning of the      */
  606.     /* object.  Set sz to the size of the object in words.             */
  607.     /* Set is_atomic and hhdr.                             */
  608. #     define CONTINUE_M continue
  609. #     ifdef BLACK_LIST
  610. #    define CONTINUE goto register_bad;
  611. #     else
  612. #    define CONTINUE continue
  613. #     endif
  614. #     include "GCcheck_ptr.c"
  615. #     undef CONTINUE
  616. #     undef CONTINUE_M
  617.  
  618.  
  619. #   ifdef DEBUG2
  620.     GC_vprintf("*** set bit for heap %x, word %x\n",h,word_no);
  621. #   endif
  622. #   ifdef SEPARATE_HEADERS
  623.       set_mark_bit_from_hdr(hhdr, word_no);
  624. #   else
  625.       set_mark_bit(h, word_no);
  626. #   endif
  627. #   ifdef VISUALIZE
  628.     displayMark(p, sz);
  629. #   endif
  630. #   ifdef GATHERSTATS
  631.       GC_my_objects_in_use_reg++;
  632. #   endif
  633.     if (is_atomic) {
  634.     /* Atomic object */
  635. #      ifdef GATHERSTATS    
  636.         GC_my_atomic_in_use += sz;
  637. #      endif        
  638.       continue;
  639.     }
  640.     GC_my_composite_in_use += sz;
  641.     {
  642.       /* Mark from fields inside the object */
  643.     register struct obj ** q;
  644.     register struct obj * r;
  645.     register long lim;   /* Should be struct obj **, but we're out of */
  646.                  /* A registers on a 68000.                   */
  647.  
  648. #       ifdef INTERIOR_POINTERS
  649.       /* Adjust p, so that it's properly aligned */
  650.         p = ((struct obj *)(((word *)h) + word_no));
  651. #       endif
  652. #       ifdef UNALIGNED
  653.       lim = ((long)(&(p -> obj_component[sz]))) - 3;
  654. #       else
  655.       lim = (long)(&(p -> obj_component[sz]));
  656. #       endif
  657.     for (q = (struct obj **)(&(p -> obj_component[0]));
  658.                     q < (struct obj **)lim;) {
  659.         r = *q;
  660.         if (quicktest(r)) {
  661. #               ifdef DEBUG2
  662.             GC_vprintf("Found plausible nested pointer");
  663.             GC_vprintf(": 0x%X inside 0x%X at 0x%X\n", r, p, q);
  664. #               endif
  665.         PUSH_MS(((word)r));
  666.         }
  667. #           ifdef UNALIGNED
  668.         q = ((struct obj **)(((long)q)+alignment));
  669. #           else
  670.         q++;
  671. #           endif 
  672.     }
  673.     }
  674.  
  675. #   ifdef VISUALIZE
  676.      /* show marked objects */
  677.       for (i = 0; i < MAP_SIZE; i++) {
  678.     if (hblkmap[i] == HBLK_VALID && GC_dirty_bits[i+offset]) {
  679.         hbp = (struct hblk *)(HBLKSIZE * i + GC_heapstart);
  680.         sz = hb_sz(hbp);
  681.         if (sz < 0) {
  682.         continue;
  683.         }
  684.         if (sz > MAXOBJSZ &&
  685.         mark_bit(hbp, (hbp -> hb_body) - ((word *)(hbp))) ) {
  686.         displayMark(hbp -> hb_body, sz);
  687.         } else {
  688.         /* Small composite objects */
  689.         p = (word *)(hbp->hb_body);
  690.         word_no = p - ((word *)hbp);
  691.         plim = (word *)((((unsigned)hbp) + HBLKSIZE)
  692.              - WORDS_TO_BYTES(sz));
  693.         for (; p <= plim; p += sz, word_no += sz) {
  694.             if (mark_bit(hbp, word_no)) {
  695.             displayMark(p, sz);
  696.             }
  697.         }
  698.         }
  699.     }
  700.       }
  701. #   endif
  702. # ifdef BLACK_LIST
  703.     continue;
  704.     register_bad:
  705.         /* p looks like a pointer, but doesn't point to an    */
  706.         /* objects.                        */
  707.         if ((unsigned long)p
  708.             >= (unsigned long) ((struct hblk *) GC_heapstart + MAP_SIZE)) {
  709.             continue;
  710.         }
  711.         GC_add_to_black_list(p);
  712. # endif
  713.   }
  714.   
  715. # undef GC_heapstart
  716. # undef GC_mark_stack_top
  717.   GC_mark_stack_top = GC_mark_stack_top_reg;
  718. # ifdef GATHERSTATS
  719.     GC_my_objects_in_use = GC_my_objects_in_use_reg;
  720. # endif
  721.   
  722.   markfaults = GC_check_faults()-startfaults;
  723.   GC_markfaults += markfaults;
  724. # ifdef COUNT_CACHE_HITS
  725.     GC_vprintf("%d map cache hits, %d misses\n", 
  726.               map_cache_hits, map_cache_misses);
  727. # endif
  728.  
  729. # ifdef PRINTSTATS
  730.     if (markfaults > 0) {
  731.       GC_vprintf("Generated %d page faults during marking\n", markfaults);
  732.     }
  733. # endif
  734.   }
  735.  
  736. static void GC_mark_all_worker();
  737. static void GC_mark_all_with_coercion_worker();
  738.  
  739.  
  740. /*********************************************************************/
  741. /* Push all possible pointers between b and t onto the mark stack.   */
  742. /* A subsequent call to mark will then                      */
  743. /* mark all locations reachable via pointers located between b and t */
  744. /* b is the first location to be checked. t is one past the last     */
  745. /* location to be checked.                                           */
  746. /* Assume that pointers are aligned on alignment-byte                */
  747. /* boundaries.                                 */
  748. /* Treat clean pages or pages with unknown dirty status according    */
  749. /* to whether mark_clean is ALL_POINTERS, POSSIBLY_DIRTY_POINTERS,   */
  750. /* or DEFINITELY_DIRTY_POINTERS.                     */    
  751. /* If coerce_pointers is TRUE, then try to coerce pointers to         */
  752. /* valid object addresses berfore pushing them.                 */
  753. /* The coercion involves translating an arbitrary pointer to the     */
  754. /* middle of an object into a pointer to the object beginning.         */
  755. /*********************************************************************/
  756. void GC_mark_all(b, t, alignment, mark_clean, coerce_pointers)
  757. word * b;
  758. word * t;
  759. int alignment;
  760. int mark_clean;
  761. bool coerce_pointers;
  762. {
  763. #   ifdef DEBUG
  764.     GC_vprintf("Checking for pointers between 0x%X and 0x%X\n",
  765.         b, t);
  766. #   endif
  767.  
  768.   /* Round b down so it is properly aligned */
  769. #   ifdef UNALIGNED
  770.       if (alignment == 2) {
  771.         b = (word *)(((long) b) & ~1);
  772.       } else if (alignment == 4) {
  773.     b = (word *)(((long) b) & ~3);
  774.       } else if (alignment != 1) {
  775.     GC_abort("Bad alignment parameter to GC_mark_all");
  776.       }
  777. #   else
  778.       b = (word *)(((long) b) & ~3);
  779. #   endif
  780.     if (mark_clean == ALL_POINTERS) {
  781.         if (coerce_pointers) {
  782.             GC_mark_all_with_coercion_worker(b, t, alignment);
  783.         } else {
  784.             GC_mark_all_worker(b, t, alignment);
  785.         }
  786.     } else {
  787.     register unsigned long VD_base_reg
  788.                       = (unsigned long) VD_base;
  789.                       
  790.     if (b >= (word *)VD_base_reg && t <= (word *)GC_heaplim) {
  791.       register unsigned long l = (unsigned long)b;
  792.       register unsigned long u = ((unsigned long)HBLKPTR(l)) + HBLKSIZE;
  793.       register int index;
  794.       
  795.       while (l < (unsigned long)t)  {
  796.         if (u > (unsigned long)t) {
  797.           u = (unsigned long)t;
  798.         }
  799.         index = divHBLKSZ(((unsigned long)l)
  800.                           - ((unsigned long) VD_base_reg));
  801.         if (GC_dirty_bits[index]) {
  802.           if (coerce_pointers) {
  803.               GC_mark_all_with_coercion_worker(l, u, alignment);
  804.           } else {
  805.               GC_mark_all_worker(l, u, alignment);
  806.           }
  807.         }
  808.         l = u;
  809.         u += HBLKSIZE;
  810.       }
  811.     } else if (mark_clean == POSSIBLY_DIRTY_POINTERS) {
  812.       if (coerce_pointers) {
  813.           GC_mark_all_with_coercion_worker(b, t, alignment);
  814.       } else {
  815.           GC_mark_all_worker(b, t, alignment);
  816.       }
  817.     } else if (mark_clean != DEFINITELY_DIRTY_POINTERS) {
  818.       GC_abort("Bad argument to GC_mark_all\n");
  819.     }
  820.     }
  821. }
  822.  
  823.  
  824. static void GC_mark_all_worker(b, t, alignment)
  825. word *b;
  826. word *t;
  827. int alignment;
  828. {
  829.     register word *p;
  830.     register word r;
  831.     register word *lim;
  832.     /* Register copies of frequently referenced globals */
  833.     /* Referenced primarily from inside macros.         */
  834.       register char * GC_heapstart_reg = GC_heapstart;
  835.       register word * GC_mark_stack_top_reg = GC_mark_stack_top;
  836. #   define GC_heapstart GC_heapstart_reg
  837. #   define GC_mark_stack_top GC_mark_stack_top_reg      
  838.  
  839.   /* check all pointers in range and put on mark_stack if quicktest true */
  840.     lim = t - 1 /* longword */;
  841.     for (p = b; ((unsigned) p) <= ((unsigned) lim);) {
  842.         /* Coercion to unsigned in the preceding appears to be necessary */
  843.         /* due to a bug in the 4.2BSD C compiler.                        */
  844.     r = *p;
  845.     if (quicktest(r)) {
  846. #           ifdef DEBUG2
  847.         GC_vprintf("Found plausible pointer: %X\n", r);
  848. #           endif
  849.         PUSH_MS(r);         /* push r onto the mark stack */
  850.     }
  851. #       ifdef UNALIGNED
  852.       p = (word *)(((char *)p) + alignment);
  853. #       else
  854.       p++;
  855. #       endif
  856.     }
  857. #   undef GC_heapstart
  858. #   undef GC_mark_stack_top
  859.     GC_mark_stack_top = GC_mark_stack_top_reg;
  860. }
  861.  
  862.  
  863. static void GC_mark_all_with_coercion_worker(b, t, alignment)
  864. word *b;
  865. word *t;
  866. int alignment;
  867. {
  868.     register word *p;
  869.     register word r;
  870.     register word *lim;
  871.     register struct hblk * h;
  872.     register long sz;
  873.     register long word_no;
  874.     /* Register copies of frequently referenced globals */
  875.     /* Referenced primarily from inside macros.         */
  876.       register char * GC_heapstart_reg = GC_heapstart;
  877.       register char * GC_heaplim_reg = GC_heaplim;
  878.       register word * GC_mark_stack_top_reg = GC_mark_stack_top;
  879. #   define GC_heapstart GC_heapstart_reg
  880. #   define GC_mark_stack_top GC_mark_stack_top_reg      
  881.  
  882.   /* check all pointers in range and try to coerce to object pointers.  */
  883.   /* Put resulting pointers on mark stack.                */
  884.     lim = t - 1 /* longword */;
  885.     for (p = b; ((unsigned) p) <= ((unsigned) lim);) {
  886.     r = *p;
  887.     if (quicktest(r) && (char *)r < GC_heaplim_reg) {
  888. #           ifdef DEBUG2
  889.         GC_vprintf("Found plausible pointer: %X\n", r);
  890. #           endif
  891.         h = HBLKPTR(r);
  892.         if (!is_hblk(h)) {
  893.             char m = get_map(h);
  894.             while (m > 0 && m < 0x7f) {
  895.                 h -= m;
  896.                 m = get_map(h);
  897.             }
  898.             if (!is_hblk(h)) {
  899.                 goto next_p;
  900.             }
  901.             }
  902.             sz = hb_sz(h);
  903.             if (sz < 0) sz = -sz;
  904.             if (sz > MAXOBJSZ) {
  905.                r = ((word)h) + HDR_BYTES;
  906.             } else {
  907.                word_no = WORD_NO(r, h);
  908.                word_no = adjusted_word_no(word_no,sz);
  909.                r = (word)((word *)h + word_no);
  910.             }
  911.         PUSH_MS(r);         /* push r onto the mark stack */
  912.     }
  913.       next_p:
  914.  
  915. #       ifdef UNALIGNED
  916.       p = (word *)(((char *)p) + alignment);
  917. #       else
  918.       p++;
  919. #       endif
  920.     }
  921. #   undef GC_heapstart
  922. #   undef GC_mark_stack_top
  923.     GC_mark_stack_top = GC_mark_stack_top_reg;
  924. }
  925.